package SubjectTree.Two;

import java.util.LinkedList;
import java.util.Queue;

import Utility.TreeNode;

public class IsSymmetric {

/**
 * 难度：简单
 * 
 * 101. 对称二叉树
 * 	给定一个二叉树，检查它是否是镜像对称的。
 * 
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *      1
 *     / \
 *    2   2
 *   / \ / \
 *  3  4 4  3
 * 	但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * 	    1
 * 	   / \
 * 	  2   2
 * 	   \   \
 * 	   3    3
 * 
 * 进阶：
 * 	你可以运用递归和迭代两种方法解决这个问题吗？
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsSymmetric tis=new IsSymmetric();
		TreeNode root = TreeNode.MkTree("[1,2,2,3,4,4,3]");
		System.out.println(tis.isSymmetric(root));
	}
	
	
	public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
	//自己写
	public boolean check(TreeNode p, TreeNode q) {
		// 首先排除空节点的情况
		if(p==null && q!=null)return false;
		else if(p!=null && q==null)return false;
		else if(p==null && q==null)return true;
		// 排除了空节点，再排除数值不相同的情况
		else if(p.val != q.val)return false;
		
		// 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
		boolean outside = check(p.left,q.right);	// 左子树：左、 右子树：右
		boolean inside = check(p.right,q.left);		// 左子树：右、 右子树：左
		boolean isSame = outside && inside;			// 左子树：中、 右子树：中 （逻辑处理）
		return isSame;
	}
	//方法一：递归
    public boolean check1(TreeNode p, TreeNode q) {
//    	System.out.println(p+","+q);
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check1(p.left, q.right) && check1(p.right, q.left);
    }
    //方法二：迭代
    public boolean check2(TreeNode u, TreeNode v) {
    	Queue<TreeNode> q = new LinkedList<>();
    	q.offer(u);
    	q.offer(v);
    	while(!q.isEmpty()) {
    		u=q.poll();
    		v=q.poll();
    		if(u==null&&v==null) {
    			continue;
    		}
    		if(u==null||v==null||(u.val!=v.val)) {
    			return false;
    		}
    		
    		q.offer(u.left);
    		q.offer(v.right);
    		
    		q.offer(u.right);
    		q.offer(v.left);
    	}
    	
    	return true;
    }
}
